package pro.softzhang.algo.lc200;

import pro.softzhang.algo.flag.knowledge.KSort;

import java.util.Random;

/**
 * 215. 数组中的第K个最大元素
 * https://leetcode.cn/problems/kth-largest-element-in-an-array
 */
public class LC215_KthLargestElementInAnArray {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Solution {
        private Random random = new Random();

        public int findKthLargest(int[] nums, int k) {
            int target = nums.length - k;
            int start = 0, end = nums.length - 1;
            int idx = partition(nums, start, end);
            while (idx != target) {
                if(idx > target) {
                    end = idx - 1;
                } else {
                    start = idx + 1;
                }
                idx = partition(nums, start, end);
            }
            return nums[idx];
        }

        private int partition(int[] nums, int start, int end) {
            int rn = random.nextInt(end - start + 1) + start;
            swap(nums, rn, end);

            int small = start - 1;
            for (int i = start; i < end; i++) {
                if(nums[i] < nums[end]) {
                    small++;
                    swap(nums, i, small);
                }
            }

            small++;
            swap(nums, small, end);
            return small;
        }

        private void swap(int[] nums, int idx1, int idx2) {
            if(idx1 != idx2) {
                int tmp = nums[idx1];
                nums[idx1] = nums[idx2];
                nums[idx2] = tmp;
            }
        }
    }

    /**
     * 桶排序
     */
    @KSort
    static
    class Solution1 {
        public int findKthLargest(int[] nums, int k) {
            int[] buckets = new int[20001];
            for (int num : nums) {
                buckets[num + 10000]++;
            }
            for (int i = 20000; i >= 0; i--) {
                k = k - buckets[i];
                if (k <= 0) {
                    return i - 10000;
                }
            }
            return 0;
        }
    }
}